P2668 斗地主

此题的唯一精髓：搜索模拟

为了模拟方便，这里的3处理为1 ， K处理为11 ， 1处理为12 , 2处理为13 。

注意

1:大小王不能当对子打出。除了顺子大小王可以当做单张打出。

2:四带二可以用两张相同单牌

唯一的剪枝：当只剩下对子和单张可以打的时候，可以直接扫一遍统计出答案。

再加上最优性剪枝，就可以AC此题了。

#include <cstdio>
#include <iostream>
using namespace std;

const int MAXD = 15;
int t , n , x , y , cnt[ 20 ] , Ans;

bool check( ) {
	for( int i = 1 ; i <= MAXD ; i ++ )
		if( cnt[ i ] ) return 0;
	return 1;
}
void dfs( int step ) {
	if( step >= Ans ) return;
	if( check( ) ) {
		Ans = step;
		return;
	}
	
	if( cnt[ 14 ] == 1 && cnt[ 15 ] == 1 ) { //火箭
		cnt[ 14 ] = cnt[ 15 ] = 0;
		dfs( step + 1 );
		cnt[ 14 ] = cnt[ 15 ] = 1;
	}
	
	int l1 = 0 , l2 = 0 , l3 = 0;
	for( int i = 1 ; i <= MAXD - 3 ; i ++ ) { //顺子
		l1 = cnt[ i ] >= 1 ? l1 + 1 : 0;
		l2 = cnt[ i ] >= 2 ? l2 + 1 : 0;
		l3 = cnt[ i ] >= 3 ? l3 + 1 : 0;
		
		if( l1 >= 5 ) {	//单顺子
			for( int len = 5 ; len <= l1 ; len ++ )
				for( int sta = i - l1 + 1 ; sta + len - 1 <= i ; sta ++ ) {
					for( int dex = sta ; dex <= sta + len - 1 ; dex ++ )
						cnt[ dex ] --;
					dfs( step + 1 );
					for( int dex = sta ; dex <= sta + len - 1 ; dex ++ )
						cnt[ dex ] ++;
				}
		}
		if( l2 >= 3 ) {	//双顺子
			for( int len = 3 ; len <= l2 ; len ++ )
				for( int sta = i - l2 + 1 ; sta + len - 1 <= i ; sta ++ ) {
					for( int dex = sta ; dex <= sta + len - 1 ; dex ++ )
						cnt[ dex ] -= 2;
					dfs( step + 1 );
					for( int dex = sta ; dex <= sta + len - 1 ; dex ++ )
						cnt[ dex ] += 2;
				}
		}
		if( l3 >= 2 ) {	//三顺子
			for( int len = 2 ; len <= l3 ; len ++ )
				for( int sta = i - l3 + 1 ; sta + len - 1 <= i ; sta ++ ) {
					for( int dex = sta ; dex <= sta + len - 1 ; dex ++ )
						cnt[ dex ] -= 3;
					dfs( step + 1 );
					for( int dex = sta ; dex <= sta + len - 1 ; dex ++ )
						cnt[ dex ] += 3;
				}
		}
	}
	for( int i = 1 ; i <= MAXD ; i ++ ) {
		if( cnt[ i ] >= 3 ) {
			cnt[ i ] -= 3;
			dfs( step + 1 );//三张牌
			
			for( int dex = 1 ; dex <= MAXD ; dex ++ )
				if( cnt[ dex ] && dex != i ) { //三带二
					if( cnt[ dex ] >= 2 ) {
						cnt[ dex ] -= 2;
						dfs( step + 1 );
						cnt[ dex ] += 2;
					}
					if( cnt[ dex ] >= 1 ) { //三代一
						cnt[ dex ] --;
						dfs( step + 1 );
						cnt[ dex ] ++;
					}
				}
            cnt[ i ] += 3;
		}
        if( cnt[ i ] >= 4 ) {
			
			cnt[ i ] -= 4;//炸弹
			dfs( step + 1 );

			for( int dex1 = 1 ; dex1 <= MAXD ; dex1 ++ )
				if( cnt[ dex1 ] && dex1 != i )
					for( int dex2 = dex1 ; dex2 <= MAXD ; dex2 ++ )
						if( cnt[ dex2 ] && dex2 != i ) {
							if( cnt[ dex1 ] >= 1 && cnt[ dex2 ] >= 1 ) {//四代2张单牌
								cnt[ dex1 ] -- , cnt[ dex2 ] --;
								dfs( step + 1 );
								cnt[ dex1 ] ++ , cnt[ dex2 ] ++;
							}
							if( cnt[ dex1 ] >= 2 && cnt[ dex2 ] >= 2 ) { //四代2双对子
								cnt[ dex1 ] -= 2 , cnt[ dex2 ] -= 2;
								dfs( step + 1 );
								cnt[ dex1 ] += 2 , cnt[ dex2 ] += 2;
							}
						}
            cnt[ i ] += 4;
		}
	}

    int res = 0;
    for( int i = 1 ; i <= MAXD ; i ++ )
        if( cnt[ i ] ) res ++;
    Ans = min( Ans , step + res );	//唯一的剪枝
}
int main( ) {
	scanf("%d %d",&t,&n);
	while( t -- ) {
		Ans = n;
        for( int i = 1 ; i <= MAXD ; i ++ ) cnt[ i ] = 0;
		for( int i = 1 ; i <= n ; i ++ ) {
			scanf("%d %d",&x,&y);
			if( x == 0 ) cnt[ 13 + y ] ++;
            if( x == 1 ) cnt[ 12 ] ++;
			if( x == 2 ) cnt[ 13 ] ++;
			if( x >= 3 ) cnt[ x - 2 ] ++;
		}
        //for( int i = 1 ; i <= 15 ; i ++ )
        //    printf("%d %d\n",i,cnt[ i ]);
		dfs( 0 );
		printf("%d\n", Ans );
	}
	return 0;
}